// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

// impl ListNode {
//     #[inline]
//     fn new(val: i32) -> Self {
//         ListNode { next: None, val }
//     }
// }

struct Solution;

impl Solution {
    /// 自己解法 2021.2.19 错误的解法
    /// 理解错了题意，需要的是下一个比自己大的数，而不是接下来比自己大且最大的数
    fn next_larger_help_self(head: Box<ListNode>, vec: &mut Vec<i32>) -> i32 {
        if let Some(next) = head.next {
            let next_val = Solution::next_larger_help_self(next, vec);
            if next_val > head.val {
                vec.push(next_val);
                next_val
            } else {
                vec.push(0);
                head.val
            }
        } else {
            vec.push(0);
            head.val
        }
    }

    pub fn next_larger_nodes_self(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut res = vec![];
        if let Some(head) = head {
            Solution::next_larger_help_self(head, &mut res);
        }
        res.reverse();
        res
    }

    /// 根据评论区Java解法得到
    pub fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut vec = vec![];
        let mut head = head.unwrap();
        loop {
            vec.push(head.val);
            if let Some(next) = head.next {
                head = next;
            } else {
                break;
            }
        }
        let len = vec.len();
        let mut res = vec![0; len];
        let mut stack = vec![];
        for i in 0..vec.len() {
            while !stack.is_empty() && vec[*stack.last().unwrap()] < vec[i] {
                println!("{} {}", *stack.last().unwrap(), vec[i]);
                res[stack.pop().unwrap()] = vec[i];
            }
            stack.push(i)
        }

        res
    }
}

fn main() {
    Solution::next_larger_nodes_self(None);
    Solution::next_larger_nodes(None);
}
